package main.leetcode.offer.firstround.from03to50;

/**
 * 16.数值的整次方
 *
 * <p>实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
 *
 * <p>
 *
 * <p>示例 1: 输入: 2.00000, 10 输出: 1024.00000
 *
 * <p>示例 2: 输入: 2.10000, 3 输出: 9.26100
 *
 * <p>示例 3: 输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
 *
 * <p>说明: -100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex16 {
    public static void main(String[] args) {
        System.out.println(new ex16().myPow(2, 100000));
    }

    // 快速幂——将指数看成二进制数
    public double myPow1(double x, int n) {
        if (n == 1 || x == 0 || x == 1) return x;
        if (n == 0) return 1;
        long tn = n;
        if (tn < 0) {
            x = 1 / x;
            tn = -tn;
        }
        double res = 1.0;
        while (tn > 0) {
            if ((tn & 1) == 1) res *= x; // tn为奇数，右移一位（即除2）后会少一位
            x *= x;
            tn >>= 1; // tn的二进制位数相当于平方次数
        }
        return res;
    }

    // 递归———分治思想
    public double myPow(double x, int n) {
        if (n == 1 || x == 0 || x == 1) return x;
        if (n == 0) return 1;
        long tn = n; // 给出的 n 可以取到 -2147483648−2147483648（整型负数的最小值），因此，在编码的时候，需要将 n 转换成 long 类型
        if (n < 0) return myPow(1 / x, -tn);
        return myPow(x, tn);
    }

    private double myPow(double x, long n) {
        if (n == 0) return 1;
        double square;
        if ((n & 1) == 0) { // 双数
            /** 右移其实就是除2，所以拿到一个square之后直接平方就行 */
            square = myPow(x, n >>> 1); // 分
            return square * square; // 合
        } else { // 奇数
            /** 一个道理，但是奇数在初二的过程中少了丢了最后一个1，所以还要乘回去一个x */
            square = myPow(x, (n - 1) >>> 1);
            return square * square * x;
        }
    }
}
